package business.util;
public class CircularLinkedList< E> {
    private Node< E> head;
    private int length;        //the length of the list
    
    public CircularLinkedList() {
        head = new Node< E>(null, head);
        length = 0;
    }
    
    
    
    public Node<E> getHead() {
		return head;
	}



	public void setHead(Node<E> head) {
		this.head = head;
	}



	public void insertAtPrior(E item) {//在头节点之后加一个节点
        Node< E> node = new Node< E>(item, null);    //encpsule the item to an node
        node.setNext(head.getNext());    //node.next = head.next
        head.setNext(node);    //head.next = node
        length ++;
    }
    
    public void add(E item) {//在最后节点上添加一个节点
        
        Node< E> tmp = head;
        
        if (isEmpty()) {    // if the list is null
            Node< E> node = new Node< E>(item, head);    // .. if next == null ?
            head.setNext(node);
        } else {
            Node< E> node = new Node< E>(item, head);
            // find the end node of the list 
            while (head != tmp.getNext()) {
                tmp = tmp.getNext();
            }
            tmp.setNext(node);
        }
        
        length++;
    }
    
     public E get(int index) { //获取索引处的节点的数据
       // 先判断索引正确性   
        if (index >length || index < 0) {   
          throw new RuntimeException("索引值有错：" + index);   
        }else if(isEmpty()){
            return null;
        }else{
          Node< E> tmp =head;   
          int i= 1;   
          while (head != tmp.getNext() && i <= index) {
                tmp = tmp.getNext();
                i++;
            }
           E e = tmp.getData();   
          return e;   
       }
    }   
    public void insert(int index, E item) {//在索引处后添加节点
        Node< E> node = new Node< E>(item, null);
        Node< E> tmp = head;
        int i = 1;
        
        if (index > length || index < 0) {
            System.out.println("the index is out of bounds");
        } else if (0 == length && 1 == index) {
            node.setNext(head);
            head.setNext(node);
            length++;
        } else {
            //find the node index
            while (head != tmp.getNext() && i <= index) {
                tmp = tmp.getNext();
                i++;
            }
            node.setNext(tmp.getNext());
            tmp.setNext(node);
            length++;
        }
    }
    
    public void removeFromFront() {//删除头节点之后的第一个节点
        Node< E> tmp = head;
        if (length < 1) {
            System.out.println("The list is null and you can not delete any node!");
        } else if (1 == length) {
            head.setNext(head);
            length--;
        } else {
            head.setNext(tmp.getNext().getNext());
            length--;
        }
    }
    
    public void remove(int index) {//删除索引处的节点
        if (length < 1 || index > length) {
            System.out.println("index is out of bounds");
        } else if (1 == length && 1 == index) {
            head.setNext(head);
            length--;
        } else {
            Node< E> tmp = head;
            int i = 1;
            
            //get the node before index
            while (head != tmp.getNext() && i < index) {
                tmp = tmp.getNext();
                i++;
            }
            tmp.setNext(tmp.getNext().getNext());
            length--;
        }
    }
    
    
    public void removeFromLast() {//删除最后一个节点
        if (length < 1) {     // if the list is null
            System.out.println("The list is null and you can not delete");
        } else if (1 == length) {
            head.setNext(head);
            length--;
        } else {
            Node< E> tmp1 = head;
            Node< E> tmp2 = head.getNext(); //set tmp2 -tmp1 = 1 
            
            while (head != tmp2.getNext()) {
                tmp2 = tmp2.getNext();
                tmp1 = tmp1.getNext();
            }
            tmp1.setNext(head);
            length--;
        }
    }
    
    
    public int getLength() {
        return length;
    }
    
    public boolean isEmpty() {
          return length==0;
    }
    
    
    public void display() {
        if (length < 1) {
            System.out.println("The list is null");
        } else {
            Node< E> tmp = head;
            while (head != tmp.getNext()) {
                tmp = tmp.getNext();
                System.out.print(tmp.getData() + " ");
            }
        }
    }
    //test the list
    public static void main(String[] args) {
        CircularLinkedList< Integer> l = new CircularLinkedList< Integer>();
        System.out.println(l.isEmpty());
        l.add(1);
        l.add(2);
        l.insertAtPrior(3);
        l.insert(2, 4);
        l.add(5);
        System.out.println("the list is : ");
        l.display();
        while(l.getHead().getNext()!=null){
        	System.out.println(l.getHead().getData());
        }
//        System.out.println();
//        System.out.println("the length is :" + l.getLength());
//        l.removeFromFront();
//        l.removeFromLast();
//        l.display();
        
       // System.out.println(l.get(3));
    }
}
